package bin_tree;

import java.util.NoSuchElementException;

/**
 * 基于int的二分搜索树，不包含重复元素
 * @author yuisama
 * @date 2022/01/15 09:31
 **/
public class BST {
    // 结点个数
    private int size;
    // 根节点
    private Node root;
    // 结点定义
    private class Node {
        private int val;
        private Node left;
        private Node right;

        public Node(int val) {
            this.val = val;
        }
    }
    // 向BST中添加一个新元素，用户使用
    public void add(int value) {
        root = add(root,value);
    }
    /**
     * 向以root为根节点的BST中添加一个新元素value
     * @param root
     * @param value
     * @return 返回添加元素后的根节点
     */
    private Node add(Node root, int value) {
        // 当root为空时，此时走到叶子结点，创建新节点插入值
        if (root == null) {
            root = new Node(value);
            size ++;
            return root;
        }
        // 比较value和根节点的大小
        if (value < root.val) {
            // 在左树中添加
            root.left = add(root.left,value);
            return root;
        }
        root.right = add(root.right,value);
        return root;
    }

    public boolean contains(int val) {
        return contains(root,val);
    }

    /**
     * 判断以root为根节点的BST中是否包含指定元素val
     * @param root
     * @param val
     * @return
     */
    private boolean contains(Node root, int val) {
        if (root == null) {
            return false;
        }
        // 根节点恰好就是待查找的值
        else if (root.val == val) return true;
        // 左树中找
        else if (val < root.val) return contains(root.left,val);
        // 右树中找
        return contains(root.right,val);
    }

    public int maximum() {
        if (size == 0){
            throw new NoSuchElementException("bst is empty!");
        }
        // 找到最大值所在的结点
        Node maxNode = maximum(root);
        return maxNode.val;
    }

    /**
     * 找到以当前root为根节点的BST中的最大值结点
     * @param root
     * @return
     */
    private Node maximum(Node root) {
        if (root.right == null) {
            // 此时右孩子为空，则root就是最大值结点
            return root;
        }
        return maximum(root.right);
    }

    public int minimum() {
        if (size == 0) {
            throw new NoSuchElementException("bst is empty!");
        }
        Node minNode = minimum(root);
        return minNode.val;
    }

    private Node minimum(Node root) {
        if (root.left == null) {
            return root;
        }
        return minimum(root.left);
    }
    // 删除最小值结点并返回值
    public int removeMin() {
        int val = minimum();
        root = removeMin(root);
        return val;
    }
    /**
     * 删除以当前root为根节点的BST中的最小值结点
     * 返回删除后的根节点
     * @param root
     */
    private Node removeMin(Node root) {
        if (root.left == null) {
            // 此时root为最小值结点
            // 将右树返回
            Node right = root.right;
            // 断枝 = 链表删除时，node.next = null;
            root.right = null;
            size --;
            return right;
        }
        root.left = removeMin(root.left);
        return root;
    }

    public int removeMax() {
        int max = maximum();
        root = removeMax(root);
        return max;
    }
    /**
     * 删除以当前root为根节点的BST的最大值结点
     * @param root
     * @return
     */
    private Node removeMax(Node root) {
        if (root.right == null) {
            Node left = root.left;
            root.left = null;
            size --;
            return left;
        }
        root.right = removeMax(root.right);
        return root;
    }

    public void remove(int val) {
        root = remove(root,val);
    }

    /**
     * Hibbard Deletion
     * 在以root为根节点的二叉树中删除值为val的结点
     * 返回删除后的根节点
     * @param root
     * @param val
     * @return
     */
    private Node remove(Node root, int val) {
        if (root == null) {
            // 都把BST遍历完了也没找到值为val的结点
            return null;
        }else if (val < root.val) {
            // 在左树删除
            root.left = remove(root.left,val);
            return root;
        }else if (val > root.val) {
            // 在右树删除
            root.right = remove(root.right,val);
            return root;
        }else {
            // 此时root就是待删除的结点
            if (root.left == null) {
                // 只有右孩子，返回右孩子即可
                Node right = root.right;
                root.right = null;
                size--;
                return right;
            }
            if (root.right == null) {
                // 只有左孩子，返回左孩子即可
                Node left = root.left;
                root.left = null;
                size --;
                return left;
            }
            // 此时说明root.left != null && root.right != null
            // 找到root的后继结点
            Node successor = minimum(root.right);
            // 在右子树中删除最小值，连接为successor的右子树
            // 在右子树删除后继结点的时候已经size -- 过了
            // 此时是把root替换为successor，因此size不用再 --
            successor.right = removeMin(root.right);
            // 连接root的左子树为successor的左子树
            successor.left = root.left;
            root.left = root.right = null;
            // 返回successor即可
            return successor;
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        generateBSTString(root,0,sb);
        return sb.toString();
    }

    /**
     * 先序遍历二分搜索树
     * @param root BST的根节点
     * @param depth 当前树的深度
     * @param sb
     */
    private void generateBSTString(Node root, int depth, StringBuilder sb) {
        if (root == null) {
            sb.append(generateBSTDepth(depth)).append("NULL\n");
            return;
        }
        // 先根节点
        sb.append(generateBSTDepth(depth)).append(root.val).append("\n");
        // 递归访问左子树
        generateBSTString(root.left,depth + 1,sb);
        // 递归访问右子树
        generateBSTString(root.right,depth + 1,sb);
    }
    // 打印当前BST的深度，每进入下一层就多两个 --
    private String generateBSTDepth(int depth) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            sb.append("--");
        }
        return sb.toString();
    }
}